#include "link.h"
#include <stdlib.h>

link_t InitLink()
{
	link_t link = (link_t)malloc(sizeof(plink_t));
	if (!link)
		return NULL;
	link->node = NULL;
	link->size = 0;
	return link;
}

link_t Copy(link_t link)
{
	if (link == NULL)
		return NULL;
	link_t linkcopy = InitLink();
	if (linkcopy == NULL)
		return NULL;
	node_t* node = link->node;
	node_t* new_node = CreateNode(node->key);
	if (new_node == NULL) {
		free(linkcopy);
		return NULL;
	}
	linkcopy->node = new_node;
	linkcopy->size++;
	node = node->next;
	node_t* copynode = linkcopy->node;
	while (node != NULL) {
		new_node = CreateNode(node->key);
		if (new_node == NULL)
			break;
		copynode->next = new_node;
		copynode = copynode->next;
		node = node->next;
		linkcopy->size++;
	}
	return linkcopy;
}

int Connect(link_t link1, link_t link2)
{
	if (!link1 && !link2)
		return LINKNOTINIT;
	node_t* node1 = link1->node;
	node_t* node2 = link2->node;
	while (node1->next != NULL)
		node1 = node1->next;
	int count = 0;
	while (node2 != NULL) {
		node_t* new_node = CreateNode(node2->key);
		if (new_node == NULL)
			return count;
		node1->next = new_node;
		node1 = node1->next;
		node2 = node2->next;
		link1->size++;
	}
	return count;
}

int Append(link_t link, datatype key)
{
	if (link == NULL)
		return LINKNOTINIT;
	node_t* new_node = CreateNode(key);
	if (new_node == NULL)
		return MEMORYMALLOCFALSE;
	if (link->node == NULL)
		link->node = new_node;
	else {
		node_t* node = link->node;
		while (node->next != NULL) {
			node = node->next;
		}
		node->next = new_node;
	}
	link->size++;
	return 0;
}

int Extend(link_t link, datatype* keys, int len)
{
	if (link == NULL)
		return LINKNOTINIT;
	int index = 0;
	node_t* new_node = CreateNode(keys[index]);
	if (new_node == NULL)
		return MEMORYMALLOCFALSE;
	if (link->node == NULL) {
		link->node = new_node;
		index++;
		link->size++;
	}
	node_t* node = link->node;
	while (node->next != NULL) {
		node = node->next;
	}
	while (index < len) {
		new_node = CreateNode(keys[index]);
		if (new_node == NULL)
			return index;
		node->next = new_node;
		node = node->next;
		index++;
		link->size++;
	}
	return index;
}

int Insert(link_t link, int index, datatype key)
{
	if (link == NULL)
		return LINKNOTINIT;
	node_t* new_node = CreateNode(key);
	if (new_node == NULL)
		return MEMORYMALLOCFALSE;
	if (index <= 0) {
		new_node->next = link->node;
		link->node = new_node;
		link->size++;
		return 0;
	}
	int len = Length(link);
	node_t* temp = link->node;
	node_t* last;
	for (int i = 0; i < len && i < index; ++i) {
		last = temp;
		temp = temp->next;
	}
	last->next = new_node;
	new_node->next = temp;
	link->size++;
	return 0;
}

int Modify(link_t link, int index, datatype key)
{
	if (link == NULL)
		return LINKNOTINIT;
	if (index >= Length(link))
		return MORELENGTH;
	node_t* node = link->node;
	for (int i = 0; i < index; ++i)
		node = node->next;
	node->key = key;
}

datatype Pop(link_t link)
{
	if (link == NULL)
		return LINKNOTINIT;
	if (link->size == 0)
		return LINKISEMPTY;
	datatype key;
	if (link->size == 1) {
		key = link->node->key;
		free(link->node);
		link->node = NULL;
	} else {
		node_t* node = link->node;
		node_t* temp;
		while (node->next->next != NULL) {
			node = node->next;
		}
		temp = node->next;
		node->next = NULL;
		key = temp->key;
		free(temp);
	}
	link->size--;
	return key;
}

datatype Key(link_t link, unsigned int index)
{
	if (link == NULL)
		return LINKNOTINIT;
	int i = 0;
	node_t* node = link->node;
	do {
		if (i == index)
			return node->key;
		i++;
		node = node->next;
	} while(node != NULL);
	return MORELENGTH;
}

int Delete(link_t link, unsigned int index)
{
	if (link == NULL)
		return LINKISEMPTY;
	int len = Length(link);
	if (index >= len)
		return MORELENGTH;
	if (index == 0) {
		node_t* temp = link->node;
		link->node = link->node->next;
		free(temp);
		link->size--;
		return 0;
	}
	node_t* temp = link->node;
	node_t* last;
	for (int i = 0; i < len && i < index; ++i) {	//保存需要删除的节点和它的父节点
		last = temp;
		temp = temp->next;
	}
	last->next = temp->next;
	free(temp);
	temp = NULL;
	link->size--;
	return 0;
}

int Remove(link_t link, datatype key)
{
	if (link == NULL)
		return LINKNOTINIT;
	int del_node = 0;
	node_t* temp;
	while (link->node != NULL && key == link->node->key) {
		temp = link->node;
		link->node = link->node->next;
		free(temp);
		del_node++;
		link->size--;
	}
	node_t* node = link->node;
	while (node->next != NULL) {
		if (node->next->key == key) {
			temp = node->next;
			node->next = node->next->next;
			free(temp);
			del_node++;
			link->size--;
			continue;
		}
		node = node->next;
	}
	return del_node;
}

int Clear(link_t link)
{
	if (link == NULL)
		return LINKNOTINIT;
	node_t* node;
	while (link->node != NULL) {
		node = link->node;
		link->node = link->node->next;
		free(node);
		link->size--;
	}
	return 0;
}

int Index(link_t link, datatype key)
{
	if (link == NULL)
		return LINKNOTINIT;
	node_t* node = link->node;
	int index = 0;
	while (node != NULL) {
		if (node->key == key)
			return index;
		node = node->next;
		index++;
	}
	return -1;
}

void Sort(link_t link, _Bool modl)
{
	if (link == NULL)
		return;
	const int len = Length(link);
	datatype keys[len];
	node_t* temp = link->node;
	for (int i = 0; i < len; ++i) {
		keys[i] = temp->key;
		temp = temp->next;
	}
	sortData(keys, len);
	temp = link->node;
	for (int i = 0; i < len; ++i) {
		if (modl == TRUE)
			temp->key = keys[len - i - 1];
		else
			temp->key = keys[i];
		temp = temp->next;
	}
}

void Reverse(link_t link)
{
	if (link == NULL)
		return;
	const int len = Length(link);
	datatype keys[len];
	node_t* node = link->node;
	for (int i = 0; i < len; ++i) {
		keys[i] = node->key;
		node = node->next;
	}
	node = link->node;
	for (int i = len - 1; i >= 0; --i) {
		node->key = keys[i];
		node = node->next;
	} 
}

int Length(link_t link)
{
	if (link == NULL)
		return LINKNOTINIT;
	return link->size;
}

int Count(link_t link, datatype key)
{
	if (link == NULL)
		return LINKNOTINIT;
	int count = 0;
	node_t* node = link->node;
	while (node != NULL) {
		if (node->key == key)
			++count;
		node = node->next;
	}
	return count;
}

_Bool Equal(link_t link1, link_t link2)
{
	if (!link1 && !link2)
		return LINKNOTINIT;
	if (link1->size != link2->size)
		return FALSE;
	node_t* node1 = link1->node;
	node_t* node2 = link2->node;
	while (node1 != NULL) {
		if (node1->key != node2->key)
			return FALSE;
		node1 = node1->next;
		node2 = node2->next;
	}
	return TRUE;
}

void Destroy(link_t* link)
{
	if (link == NULL || *link == NULL)
		return;
	node_t* temp;
	while ((*link)->node != NULL) {
		temp = (*link)->node;
		(*link)->node = (*link)->node->next;
		free(temp);
	}
	free(*link);
	*link = NULL;
}

node_t* CreateNode(datatype key)
{
	node_t* node = (node_t*)malloc(sizeof(node_t));
	if (node == NULL)
		return NULL;
	node->key = key;
	node->next = NULL;
	return node;
}

void sortData(datatype* num, int len)
{
	datatype temp;
	for (int i = 0; i < len; ++ i)
		for (int j = 0; j < len - i - 1; ++j)
			if (num[j] > num[j + 1]) {
				temp = num[j];
				num[j] = num[j + 1];
				num[j + 1] = temp;
			}
}

iterator_t GetIterator(link_t link)
{
	if (link == NULL)
		return NULL;
	iterator_t iter = (iterator_t)malloc(sizeof(struct iterator_));
	if (iter == NULL)
		return NULL;
	iter->iter = link->node;
	iter->used = FALSE;
	return iter;
}

_Bool Next(iterator_t iter)
{
	if (iter == NULL)
		return FALSE;
	if (iter->used == FALSE) {
		iter->used = TRUE;
		return TRUE;
	} else if (iter->iter->next != NULL) {
		iter->iter = iter->iter->next;
		return TRUE;
	} else if (iter->iter == NULL) {
		free(iter);
		return FALSE;
	}
	return FALSE;
}

datatype GetKey(iterator_t iterator)
{
	if (iterator != NULL)
		return iterator->iter->key;
	return ITERNOTINIT;
}